|
Peterson's algorithm (AKA Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981.〔G. L. Peterson: "Myths About the Mutual Exclusion Problem", ''Information Processing Letters'' 12(3) 1981, 115–116〕 While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two,〔As discussed in ''Operating Systems Review'', January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).〕 as shown below. == The algorithm == The algorithm uses two variables, ''flag'' and ''turn''. A ''flag()'' value of ''true'' indicates that the process ''n'' wants to enter the critical section. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting ''turn'' to 0. // critical section ... // end of critical section flag() = false; | style="text-align:left"| P1: flag() = true; P1_gate: turn = 0; while (flag() && turn == 0) // critical section ... // end of critical section flag() = false; |} The algorithm does satisfy the three essential criteria to solve the critical section problem, provided that changes to the variables turn, flag(), and flag() propagate immediately and atomically. The while condition works even with preemption.〔The three criteria are mutual exclusion, progress, and bounded waiting.〔Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194〕 Since turn can take on one of two values, it can replaced by a single bit, meaning that the algorithms requires only three bits of memory. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Peterson's algorithm」の詳細全文を読む スポンサード リンク
|